This invention relates to methods for performing secure multiparty computations.
Secure multiparty computation is the process whereby a collection of n participants compute a function ƒ on secret input values such that only the final result of the computation is made known to the participants. A. C. Yao is generally credited with innovating the notion of secure multiparty computation, offering as an example the well-known Yao""s Millionaires"" Problem. See Yao, A. C., xe2x80x9cProtocols for Secure Computationsxe2x80x9d, 23rd Annual Symposium on Foundations of Computer Science, pp. 160-64, 1982. In a two-party setting, the millionaires"" problem is that of enabling two entities to determine which is wealthier, without either being able to learn any additional information about the other""s fortune. For example, suppose that Alice has A million dollars and Bob has B million dollars. The goal is to securely compute the function ƒ(A, B), where ƒ(A, B) is defined as=0 if A=B, 1 if A greater than B, and 2 if B greater than A.
All of the known methods for secure multiparty computation rely on the use of a circuit to simulate the particular function ƒ of interest. The circuit is generally viewed as being composed of two logical connectors, an XOR gate (binary addition) and an AND gate (binary multiplication), which together allow for the realization of any boolean function. These methods for secure multiparty computation simulate the function of interest by evaluating the circuit on a gate-by-gate basis. To simulate an XOR gate using these methods, participants can perform local addition on their respective shares. To simulate an AND gate, however, the computation must be distributed, a procedure that in the computational model generally involves a round of verifiable secret sharing (VSS). However, the circuits used in these approaches typically will contain many AND gates and, thus, the VSS associated with each AND gate can become computationally demanding. The known approaches therefore often yield rather impractical algorithms. Recent efforts have led to some efficiency improvements. See R. Gennaro, M. Rabin, and T. Rabin, xe2x80x9cSimplified VSS and Fast-track Multiparty Computations with Applications to Threshold Cryptographyxe2x80x9d, Proceedings of 1998 ACM Symposium on Principles of Distributed Computing, pp. 25-34, 1997. Even with these improvements, however, the computational costs for problems of interest remain high, and the impact on real-world applications has been negligible.
The above-identified problems are solved and a technical advance is achieved in the art by providing an innovative method for secure multiparty computation which dispenses with the need for extensive use of VSS. An exemplary method for secure multiparty computation includes: generating a data set based on a function to be computed, the data set comprising pairs of first data and second data; for each pair of first data and second data, encrypting the first data and the second data; randomly mixing pairs of the encrypted first data and second data; comparing encrypted input data with the encrypted first data to detect a match; and selecting encrypted second data corresponding to the detected match.
In accordance with one embodiment of the present invention, n participants to a secure multiparty computation agree upon a function ƒ to be computed and a representation of that function as a circuit with at least one gate. For each gate in the circuit, the participants generate a logical table. A logical table includes all possible input and output values for the gate to which it pertains based on the function ƒ. The participants then preferably encode the input and output values in each logical table, and pass each table through a mix network. The mix network generates a blinded table for each encoded logical table. A blinded table is similar to its corresponding encoded logical table except that now the rows of the table are randomly permuted and the input and output values in each row are individually encrypted using a public key y. The process of generating blinded tables is referred to herein as xe2x80x9cthe mixing process.xe2x80x9d
After the initial mixing process, the participants engage in xe2x80x9cthe matching process.xe2x80x9d In this regard, the participants exchange encoded and encrypted versions of their secret inputs. These inputs are encrypted using the same public key y as used during the mixing process. The participants then jointly compute the function ƒ using the secret inputs and the representative circuit. To simulate a gate in the circuit, the participants compare the encrypted inputs to the gate with each encrypted input value in the blinded table until a match is detected. In the case where the circuit is a multi-layer circuit, the encrypted inputs to the gate are either the secret inputs provided by the participants (in the case where the gate resides in the first layer of the circuit) or the outputs of an upstream gate (in the case where the gate resides in either the output layer or some intermediate layer of the circuit). When a match is detected, the corresponding output value in the matched row is taken to be the output of the gate.
The foregoing is referred to herein as the xe2x80x9cmix and matchxe2x80x9d method of secure multiparty computation. As will be understood, the mix and match method is performed in an identical manner for every gate in the circuit, irrespective of the layer in which it resides or the function being computed, until the output of the last gate is identified. The output of the last gate can then be decoded and decrypted using a shared secret key x to obtain the output of the function ƒ.
Compared with previous approaches to secure multiparty computation, the mix and match method of the present invention is conceptually simpler, and, in many cases, is more computationally efficient as well. In addition, the method is provably secure relative to the Decision Diffie-Hellman problem, with robustness against a static malicious adversary corrupting fewer than one-half of the players.
Other and further aspects of the present invention will become apparent during the course of the following description and by reference to the attached drawings.